package 力扣进阶面试题;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

public class p373查找和最小的K对数字_优先级队列 {
    public static List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {

        PriorityQueue<List<Integer>> maxheap=new PriorityQueue<>(k, new Comparator< List<Integer> >() {
            @Override
            public int compare(List<Integer> o1, List<Integer> o2) {
                return (o2.get(0)+o2.get(1)) - (o1.get(0)+o1.get(1));//建大堆
            }

        });

        for (int i = 0; i < Math.min(nums1.length,k); i++) {
            for (int j = 0; j < Math.min(nums2.length,k); j++) {

                if (maxheap.size()<k) {
                    List<Integer> couple=new ArrayList<>();
                    couple.add(nums1[i]);
                    couple.add(nums2[j]);

                    maxheap.offer(couple);
                }else {
                    List<Integer> top=maxheap.peek();
                    if ((top.get(0)+top.get(1)) > nums1[i]+nums2[j]) {
                        maxheap.poll();//出堆顶元素
                        List<Integer> couple=new ArrayList<>();
                        couple.add(nums1[i]);
                        couple.add(nums2[j]);
                        maxheap.offer(couple);
                    }
                }
            }
        }
        //前k个最小和的数字对的优先级队列构建完成

        List<List<Integer>> res=new ArrayList<>();
        for (int j = 0; j < k && !maxheap.isEmpty(); j++) {
            res.add(maxheap.poll());
        }
        return res;
    }


    public static void main(String[] args) {
        int[] num1={1};
        int[] num2={2,4,3};
        List<List<Integer>> list = kSmallestPairs(num1, num2, 2);
        System.out.println(list);
    }



}
